This invention relates generally to an affine transformation of digital imaging information and, more particularly, to a system and method of mapping an image so that data is interpolated using a simple summing procedure.
Affine transformations are used in the processing of digital images, and are performed when the user finds it necessary to manipulate a graphic image stored in memory. Transformations are performed to rotate, enlarge, or zoom in on a particular feature in the stored memory. An affine transformation rotates or translates an image by keeping straight lines straight and parallel lines parallel, but by altering the distance between points.
One popular industrial application of the affine transformation process is in the checking of product labels. Product labels are checked by computer for accuracy by comparing an image of the label taken by video camera to a template, or golden label image in computer memory. If the image sensed by the camera matches the template, the label is found acceptable by the computer and passed to the next step in the process. A problem exists, however, when the label is slightly askew. Then a number of otherwise acceptable labels will not match the template. That is, the label image on camera will appear slightly crooked in comparison to the template label in memory. Because the labels are not an exact match, the product is needlessly rejected. One method of solving this problem is to provide a large number of templates, including slightly misaligned images in memory. In this manner, a product label on camera is compared to a variety of templates until a match is found. However, this method takes a great deal of memory and slows the identification process considerably.
Another, more effective method of comparing a video image of a product label to a template is to use an affine transformation process. The video image of the crooked label is transformed until the image is made to appear "straight" with regard to the template. The transformed image is then compared to the template and, when a match occurs, the product is passed on to the next step in the process. In this manner, a wide variety of differing, but acceptable, product labels can be tested quickly against the template.
As is well known in the art, a video camera captures an image by breaking the image into a series of sequential rows starting from the top of the screen and continuing to the bottom. Brightness information is recorded in sequential and periodic locations along each row. Each location of image information is called a pixel. When a color video camera is used, many systems devote an equal number of pixels to each of the three primary colors. Typically, 256 values (8 bits) are devoted to the resolution of each pixel color. The image information is located in discrete pixel addresses which are organized to represent the image in a two dimensional (X,Y) matrix. Each pixel in this matrix can be represented by a unique X and Y coordinate, with each location separated by integer X and Y values. Each pixel address in the matrix can then be stored in digital memory. When the image is to be viewed, the memory can be accessed and the pixel information transferred to a cathode ray tube (CRT). The pixel information scanned across the CRT is organized in a manner similar to way in which it was recorded.
When the video image in memory is simply transferred from memory to the CRT, or another memory, no affine transformation process is required. That is, there is a one-for-one relationship between each pixel stored in memory and each pixel displayed on the CRT. As each sequential pixel in a row of a CRT is scanned, corresponding pixels in sequential memory addresses are accessed to transfer the pixel data.
When the image in memory is to be translated, rotated, or changed in scale, an affine transformation process is required. There is no longer a one-for-one relationship between pixel addresses in memory and the order in which the CRT is scanned. Even if the image in memory is just to be rotated, it is no longer possible to sequentially access addresses in memory. FIG. 1 depicts an image in a first memory to be transformed (prior art). FIG. 2 depicts the image of FIG. 1 after a rotation of 120 degrees clockwise, and expansion by a factor of 1.7 (prior art). To accomplish the transformation, the order in which addresses in the first memory are accessed must be changed to suit the organization of pixel information supplied to the CRT, or second memory of FIG. 2. The problem becomes further complicated when discrete pixel locations on the CRT no longer correspond to discrete locations in memory. That is, the discrete point in the transformed image, for which image information is required, falls in-between discrete pixel locations in the untransformed image. This situation requires that information from surrounding discreet locations be used in an estimation, or interpolation to supply the pixel information.
In a forward mapping transformation process, the pixel information in a discrete memory location is selected and translated to an address in a second memory system, or CRT. The address in the second system is calculated to perform the required scaling or rotation transformation. When the calculated address from the second system does not match an actual discreet address then an interpolation function must be performed. The information for the calculated address is a weighted average of pixel information associated with the surrounding discrete addresses. With inverse mapping a discrete address is selected in the second memory, or CRT, and the location of the required pixel information in the first memory system is calculated. When the calculated address in the first memory system is not a discrete address, then information from surrounding discrete addresses is supplied.
Once information is required for a particular address in the memory of the transformed image, it is well known in the art to use matrix multiplication techniques to calculate a location in the untransformed image from which information is to be obtained, for transfer to the second memory address. As mentioned above, the calculated location is usually between discrete addresses in the untransformed memory. There are also a number of well known techniques to interpolate the information from surrounding pixel addresses. Typically, these interpolation techniques require calculations of the proximity between the calculated location and surrounding pixel addresses, and numerous steps of multiplication to weight the contribution of each pixel to the average. This proportional averaging technique requires many clock cycles of processor time to complete because of the relatively complication steps of multiplication.
In the prior art multiplication process, the calculated brightness, or image information for a source location can be represented as C[X+x.sub.f, Y+y.sub.f ], calculated from discrete addresses, coordinates [X, Y], [X+1, Y], [X, Y+1], and [X+1, Y+1]. The calculated brightness is found from the sum of four products, of four weighting factors, times four brightness values. The sum of the products must always add to unity; W[X, Y]+W[X+1, Y]+W[X, Y+1]+W[X+1, Y+1]=1. ##EQU1##
For example, let x.sub.f =0.3 and y.sub.f =0.6, then ##EQU2##
As can be seen above, the multiplication process not only involves a step of summation, but also several steps of multiplication, which is very costly in processor time.
Typically, affine transformation interpolation processes are carried out through the use of software routines. Even using high speed microprocessors, or parallel processing systems, an affine transformation requires a relatively substantial amount of computer processing time. Long processing times translate to slow and clumsy applications and poor productivity. The process speed is increased by combining the software with hardware devices which quickly perform mathematical functions. However, the use of specialized hardware increases both the size and cost of the end unit.
It would be advantageous if the number of steps in the mathematical calculation of an affine transformation interpolation could be reduced to minimize the time required to perform the transformation.
It would be advantageous if an improved interpolation process required fewer, and simpler hardware devices to support mathematical calculations.
It would be advantageous if a simplified weighting procedure, eliminating multiplication steps, could be developed for use in an affine transformation.
It would be advantageous if the type of calculations performed in an interpolation process could be simplified to speed process time. Specifically, it would be advantageous if a simplified method of assigning weight to surrounding pixels could be developed, and the averaging of the weighted pixel data could be performed without multiplication.
Accordingly, a multiplication-free image data interpolation system for use in an image data processor, which transforms a first image formed in a first coordinate system into a transformed image in a second coordinate system, has been provided. The interpolation system comprises a first memory for storing first image information (I.sub.1st) as pixel data. The first memory also has an output to supply the pixel data. The system further comprises a source location calculator having an input to accept locations in the second coordinate system, from which source locations of image information (I.sup.1st) in the first coordinate system are determined and made available on a source location calculator output.
The system includes a source pixel selector having an input operatively connected to the source location calculator output, for identifying up to four pixels in the first memory from which image information (I.sup.2nd) is derived for each second image location. The source pixel selector also has an output to provide pixel identification. Further, a summing circuit having inputs operatively connected to the first memory output is included. The summing circuit sums the data (I.sup.1st) of the pixels identified by the source pixel selector, in the calculation of a weighted average for transfer to each second image location as second image information (I.sup.2nd). In this manner, image information is interpolated by a simple addition process.
In some aspects of the invention, the first memory stores first image information as pixel data (I.sup.1st) with discrete pixel addresses corresponding to locations in the first coordinate system. Then, the source locations of image information (I.sup.1st) in the first coordinate system, determined by said source location calculator, include source locations intermediately located between discrete addresses in the first memory. The source pixel selector identifies up to four pixel addresses in the first memory proximate each source location from which image information (I.sup.2nd) is derived for each second image location, and the summing circuit sums the weighted pixel data (I.sup.1st) from each selected pixel address to determine second image information (I.sup.2nd). Each weighted summation is based on the proximity of selected first memory pixel addresses and the corresponding source location within one-quarter of a discrete pixel address. The first memory pixel data (I.sup.1st) from selected proximate pixel addresses is summed in increments of one-quarter of its pixel data value. In this manner, an interpolated value is calculated for I.sup.2nd based on summing one or more values of I.sup.1st.
Specifically, the first memory stores pixel data (I.sup.1st) in discrete addresses corresponding to locations (X, Y) in the first coordinate system separated by integer X and Y increment values. The source location in the first coordinate system calculated by the source location calculator for each second image pixel address includes X and Y increment values and a predetermined number of fractional bits of partial X and Y increment values x.sub.f and y.sub.f, respectively. The source location for each second image pixel location is (X+x.sub.f, Y+y.sub.f) in the first coordinate system.
In an image data processor including a first memory to store first image information (I.sup.1st) as discrete pixel data, with each pixel having an address corresponding to a location in a first coordinate system, a multiplication-free interpolation method for transforming an image formed in the first coordinate system into a transformed image in a second coordinate system is also provided. The method comprises the steps of:
a) selecting a second image location in the second coordinate system;
b) determining a first image location in the first coordinate system corresponding to the second location selected in Step a);
c) identifying up to four pixel addresses in the first memory proximately located to the first image location determined in Step b); and
d) summing the first image pixel data (I.sup.1st) of the pixel addresses identified in Step c) in a weighted average for transfer to the second image location as second image information (I.sup.2nd), whereby first image information (I.sup.1st) is interpolated by a simple addition process .